package org.example.myleet.kmp;

public class KmpSolution {
    //p28
    /**
     * 5 ms
     * KMP算法，对needle进行预处理产生前缀数组用于对haystack进行模式匹配，时间复杂度稳定在O(m+n)，空间复杂度O(m)
     */
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        //特殊情况讨论
        if (m < n) {
            return -1;
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            char c = needle.charAt(0);
            for (int i = 0; i < m; ++i) {
                if (haystack.charAt(i) == c) {
                    return i;
                }
            }
            return -1;
        }
        //初始化next数组（前缀长度数组），i代表后缀的结束位置，j代表前缀的结束位置
        int[] next = new int[n];
        //第一位字符就是前缀的结束位置
        int j = 0;
        next[0] = j;
        //i即后缀结束位置从1开始（0位置无意义）
        for (int i = 1; i < n; ++i) {
            while (j > 0 && needle.charAt(j) != needle.charAt(i)) {
                //遇到前缀结尾与后缀结尾不匹配的情况，回退到上一个匹配的长度next[j-1]，再尝试匹配，都匹配不上时则退回到开头0
                j = next[j-1];
            }
            if (needle.charAt(j) == needle.charAt(i)) {
                //遇到前缀结尾与后缀结尾匹配的情况，j往前移动，i往前移动是在循环里面
                ++j;
            }
            next[i] = j;
        }
        //使用next数组与haystack进行匹配
        j = 0;
        for (int i = 0; i < m; ++i) {
            //原理跟next数组的初始化类似
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {
                j = next[j-1];
            }
            if (needle.charAt(j) == haystack.charAt(i)) {
                ++j;
            }
            if (j == n) {
                //特别地，当j移动到与needle的长度相同时，代表已经完整找到一个匹配的位置
                return i - (n - 1);
            }
        }
        //没找到
        return -1;
    }
}
